import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

class Solution {
    public String minWindow(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n){
            return "";
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }

        int start = 0, end = m+1, i = 0, j = 0, max = 1;
        char c;
        while (j < m && max > 0){
            while (j < m){
                c = s.charAt(j);
                if (map.containsKey(c)){
                    map.put(c, map.get(c)-1);

                    max = 0;
                    for (Map.Entry<Character,Integer> e : map.entrySet()) {
                        max = max > e.getValue()?max:e.getValue();
                        if (max > 0)
                            break;
                    }
                }
                j++;
                if (max == 0)
                    break;
            }
            if (max==0 && (end-start) > (j-i)) {
                start = i;
                end = j;
            }
            while (i < j && max == 0){
                c = s.charAt(i);
                if (map.containsKey(c)){
                    map.put(c, map.get(c)+1);
                    max = 0;
                    for (Map.Entry<Character,Integer> e : map.entrySet()) {
                        max = max > e.getValue()?max:e.getValue();
                        if (max > 0)
                            break;
                    }
                }
                
                i++;
                if (max == 0 && (end-start) > (j-i)) {
                    start = i;
                    end = j;
                }
            }
        }
        if (end==m+1)
            return "";
        return s.substring(start, end);
    }
}